import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 通天之分组背包 {
    public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static int MAXN = 1001;
    public static int MAXM = 1001;
    // arr[i][0] 存储的是 i 号物品的体积
    // arr[i][1] 存储的是 i 号物品的价值
    // arr[i][2] 存储的是 i 号物品的组号
    public static int[][] nums = new int[MAXN][3];
    public static int[][] dp = new int[MAXN][MAXM];
    public static int m,n;
    public static void main(String[] args) throws IOException {
        m = in.nextInt();
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            nums[i][0] = in.nextInt();
            nums[i][1] = in.nextInt();
            nums[i][2] = in.nextInt();
        }
        Arrays.sort(nums,1,n + 1,(a,b) -> a[2] - b[2]);
        compute();
        out.close();
    }

    private static void compute() {
        int team = 1;
        for (int i = 2; i <= n; i++) {
            if (nums[i][2] != nums[i - 1][2]) {
                team++;
            }
        }
        int[][] dp = new int[team + 1][m + 1];
        int start = 1;
        int end = 2;
        // 求 [start,end - 1] 选择 01 背包的的最大值
        // i 代表组号
        for (int i = 1; start <= n; i++) {
            // 分组然后进行 01 背包的选择操作
            while (end <= n && nums[start][2] == nums[end][2]) {
                end++;
            }
            // 0 - m 空间中的最大值
            for (int j = 0; j <= m; j++) {
                // 不选
                dp[i][j] = dp[i - 1][j];
                for (int k = start; k < end; k++) {
                    // 空间满足的时候选择货物, 需要遍历所有的货物找出最大值
                    if (j - nums[k][0] >= 0) {
                        dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - nums[k][0]] + nums[k][1]);
                    }
                }

            }
            start = end++;
        }
        out.println(dp[team][m]);
    }


    public static class Read {
        StringTokenizer st = new StringTokenizer("");
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String next() throws IOException {
            while (!st.hasMoreTokens()) {
                st = new StringTokenizer(bf.readLine());
            }
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }
}
